Semiconductor layouts comprise objects of semiconductor material, mutually connected via conducting or semiconducting material. The objects are generally polygons with edges and corners, which have coordinates in a 2-D coordinate system. The objects may be situated in different layers, making the layout a 3-D system.
Layout modification may involve, e.g., layout migration, design rule fixing or layout compaction. Layout compaction is a methodology to minimize the size of a semiconductor layout. Other modification technologies are mainly based on layout compaction, but with another optimization criterion. In a layout compaction system the main optimization criterion is the size of the layout. Optimization is performed while taking into account a set of design rules. The semiconductor layout has to fulfill several design criteria, written down as design rules and a possible additional set of (local) constraints. In 1-D compaction one changes the layout in two passes such that during the first pass edges are only moved in one dimension and such that during the second pass the edges are moved in the other dimension. During this pass the optimization problem on the layout with the given set of constraints and design rules is translated to, in general, a linear problem that can be solved with well-known algorithms.
Modifications in one dimension do however have some disadvantages. Modifications in one dimension have an effect on modifications in the other dimension. The result of 1-D modification is sub-optimal, because the problem is split into two different independent optimization problems. Furthermore, the result of the modification operation is dependent on which dimension is modified first and 2-D design rules and constraints are not taken into account.
U.S. patent application, published as US 2003/009728 and filed by David P. Marple, describes a 2-D compaction method that allows for horizontal, vertical and diagonal constraints. Diagonal constraints are non-linear in nature and therefore very difficult to solve. For enabling performing the compaction, a linear approximation of the non-linear constraints is used. Then the 2-D compaction problem is solved with a linear solver. If, after compaction, the linearization of the non-linear function appears not to be a good estimate, some additional iteration is performed to correct the layout.
It is a problem of the method of Marple and other 2-D compaction methods, that the 2-D compaction gives a lot of moving freedom and therefore it is difficult to “predict” which layout objects will be neighbors in the output result. Neighbors need to be constrained, like a minimal distance between them. So, if, in theory, every object can become a neighbor of every other object, one has to apply constraints between all pairs of layout objects. Therefore the order of the number of constraints is quadratic in the number of layout objects. With the large chip designs that we have today, this would result in a large number of constraints such that the problem becomes too large for today's computers and memories.